package com.example.demo.leetcode.top100;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _24回文链表
 * @description
 * @date 2023/06/09 16:09
 * <p>
 * ******************************************************
 */
public class _24回文链表 {

    public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        int size = 0;
        while (head != null) {
            size++;
            stack.push(head.val);
            head = head.next;
        }


        int num = 0;
        List<Integer> list = new ArrayList<>();
        while (!stack.isEmpty()) {
            if (size / 2 > num) {
                num++;
                list.add(stack.pop());
            } else {
                if (size % 2 != 0) {
                    stack.pop();
                }
                break;
            }
        }
        num = size / 2 -1;
        while (!stack.isEmpty()) {
            if (list.get(num) == stack.peek()) {
                num--;
                stack.pop();
            } else {
                return false;
            }
        }
        return true;

    }

    public static void main(String[] args) {
        ListNode head4 = new ListNode(1);
        ListNode head3 = new ListNode(2, head4);
        ListNode head2 = new ListNode(2, head3);
        ListNode head = new ListNode(1, head2);
        _24回文链表 s = new _24回文链表();
        System.out.println(s.isPalindrome(head));
    }


    public static class ListNode {
        int val;

        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

    }
}
